// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
// 法一：暴力解：每个高度向两边扩展得到最大宽度，得到该高度的面积的最大值，时间O(N2)
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int res = 0;
        for (int mid = 0; mid < n; ++mid) {
            int height = heights[mid];
            int left = mid, right = mid;
           while (left - 1 >= 0 && heights[left - 1] >= height) {
                --left;
            }
            while (right + 1 < n && heights[right + 1] >= height) {
                ++right;
            }
            // 计算面积
            res = max(res, (right - left + 1) * height);
        }
        return res;
    }
};


// 法二：单调栈：
// 单调栈讲解
// https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/
// 单调递增栈
// 1. 栈内的元素是递增的
// 2. 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
// 3. 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

// 只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。
// 这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        stack<int> s;
        int max_val = 0;
        heights.push_back(-1);
        for (int i = 0; i < heights.size(); ++i) {
            int left = i;
            while (!s.empty() && heights[s.top()] >= heights[i]) { 
                int h = heights[s.top()];
                s.pop();
                int l = s.empty() ? 0 : (s.top() + 1); // 中间没存在栈里的都是比s.top()大的
                int r = i - 1; // r就是i-1，因为如果中间有比s.top()小的，s.top()就已经被弹出了
                max_val = max(max_val, (r - l + 1) * h);
            }
            s.push(i);
        }
        return max_val;
    }
};